// 和可被k整除的子数组
class Solution
{
public:
    int subarraysDivByK(vector<int>& nums, int k) 
    {
        // 1、建表 && 初始化
        unordered_map<int, int> hash;
        hash[0 & k] = 1;
        // 2、哈希+前缀和
        int ret = 0, sum = 0;
        for(const auto e : nums)
        {
            sum += e; // 计算当前位置的前缀和
            int remain = (sum % k + k) % k; // 修正后的余数
            if(hash.count(remain)) ret += hash[remain]; // 统计结果
            ++hash[remain]; // 更新哈希表
        }
        // 3、返回值
        return ret;
    }
};

// 和为 K 的子数组
class Solution
{
public:
    int subarraySum(vector<int>& nums, int k)
    {
        // 1、建哈希表 && 初始化
        unordered_map<int, int> hash;
        hash[0] = 1;
        // 2、统计结果
        int sum = 0, ret = 0;
        for(const auto e : nums)
        {
            sum += e;
            if(hash.count(sum - k)) ret += hash[sum - k];
            ++hash[sum];
        }
        // 3、返回值
        return ret;
    }
};